#include <bits/stdc++.h>
using namespace std;
int partition(vector<int>& data,int start,int end,int length)
{
    int index = rand()%(end-start)+start;
    int small = start-1;
    swap(data[index],data[end]);
    for(int index = start;index<end;index++)
    {
        if(data[index]<data[end]) {
            small++;
            if(small != index)
                swap(data[index],data[small]);
        }
    }
    small++;
    swap(data[small],data[end]);
    return small;

}
void quick_sort(vector<int>& data,int start,int end,int length)
{
    if(start == end)
        return;
    else
    {
        int privot = partition(data,start,end,length);
        if(privot>start)
            quick_sort(data,start,privot-1,length);
        if(privot<end)
            quick_sort(data,privot+1,end,length);
    }
}
int main() {
    vector<int> a= {1,3,9,5,6,7};
    quick_sort(a,0,5,2);
    for(int i=0;i<6;i++)
        cout<<a[i]<<" ";
    return 0;
}